import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{5,4,3,2,1};
        quickSort(0, nums.length-1, nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public int findKthLargest(int[] nums, int k) {
        /**
         * 使用快速选择算法解决《数组中的第K个最大元素》*/
        return quickSelect(k, 0, nums.length-1, nums);
    }

    public int[] smallestK(int[] arr, int k) {
        quickSort(0, arr.length-1, arr);
        int[] retArray = new int[k];
        for(int i = 0; i < k; i++) {
            retArray[i] = arr[i];
        }
        return retArray;
    }

    public static Random random = new Random();

    public static void quickSort(int left, int right, int[] nums) {
        /**
         * 快速选择算法-返回数组中第K大的值*/
        // 1,递归出口
        if(left >= right) {
            return;
        }
        // 2,选择基准值（随机数）
        int key = nums[left + random.nextInt(right-left+1)];
        // 3,数组分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }
        // 4,递归剩余部分
        quickSort(left, l, nums);
        quickSort(r, right, nums);
    }

    public static int quickSelect(int k, int left, int right, int[] nums) {
        /**
         * 快速选择算法-返回数组中第K大的值*/
        // 1,递归出口
        if(left == right) {
            return nums[left];
        }
        // 2,选择基准值（随机数）
        int key = nums[left + random.nextInt(right-left+1)];
        // 3,数组分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }
        // 4,根据目标值所处区间返回
        int c = right - r + 1;
        int b = right - l;
        if(k <= c) {
            // -位于大于部分
            return quickSelect(k, r, right, nums);
        } else if(k <= b){
            // -位于等于部分
            return key;
        } else {
            // -位于小于部分
            return quickSelect(k - b, left, l, nums);
        }
    }

    public static void swap(int a, int b, int[] nums) {
        /**
         * 在数组中交换两个元素的位置*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
